/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：BinomialQueue.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-08
Function List ：
Description   ：Binomial Queue
******************************************************/

#include "BinomialQueue.h"
#include <stdlib.h>   // for malloc
#include <stdio.h>  // for printf
#include "FatalError.h"

#define Infinity (32767L)
#define MaxTrees (14)   /* Stores 2^14 -1 items */
#define Capacity (16383)

typedef struct BinNode *Position;

struct BinNode {
    ElementType Element;
    Position    LeftChild;
    Position    NextSibling;
};

struct Collection {
    int CurrentSize;
    BinTree TheTrees[MaxTrees];
};

// Static Function Lists
static void DestroyTree(BinTree T);
static BinTree CombineTrees(BinTree T1, BinTree T2);
static void PrintBinTree(BinTree T, int depth);    // for print

BinQueue Initialize(void) {
    BinQueue H;
    int i;

    H = (BinQueue)malloc(sizeof(struct Collection));
    if (H == NULL) {
        FatalError("Out of space!!!");
    }

    H->CurrentSize = 0;
    for (i = 0; i < MaxTrees; ++i) {
        H->TheTrees[i] = NULL;
    }

    return H;
}

static void DestroyTree(BinTree T) {
    if (T != NULL) {
        DestroyTree(T->LeftChild);
        DestroyTree(T->NextSibling);
        free(T);
    }
}

void Destroy(BinQueue H) {
    int i;

    for (i = 0; i < MaxTrees; ++i) {
        DestroyTree(H->TheTrees[i]);
    }
}

BinQueue MakeEmpty(BinQueue H) {
    int i;

    Destroy(H);
    for (i = 0; i < MaxTrees; ++i) {
        H->TheTrees[i] = NULL;
    }

    H->CurrentSize = 0;

    return H;
}

BinQueue Insert(ElementType Item, BinQueue H) {
    BinTree NewNode;
    BinQueue OneItem;

    NewNode = (BinTree)malloc(sizeof(struct BinNode));
    if (NewNode == NULL) {
        FatalError("Out of space!!!");
    }

    NewNode->LeftChild = NULL;
    NewNode->NextSibling = NULL;
    NewNode->Element = Item;

    OneItem = Initialize();
    OneItem->CurrentSize = 1;
    OneItem->TheTrees[0] = NewNode;

    return Merge(H, OneItem);
}

ElementType DeleteMin(BinQueue H) {
    int i;
    int j;
    int MinTree;   /* The tree with the minimum item */
    BinQueue DeletedQueue;
    Position DeletedTree;
    Position OldRoot;
    ElementType MinItem;

    if (IsEmpty(H)) {
        Error("Empty binomial queue");
        return -Infinity;
    }

    MinItem = Infinity;
    for (i = 0; i < MaxTrees; ++i) {
        if (H->TheTrees[i] != NULL &&
            H->TheTrees[i]->Element < MinItem) {
            /* Update minimum */
            MinItem = H->TheTrees[i]->Element;
            MinTree = i;
        }
    }

    DeletedTree = H->TheTrees[MinTree];
    OldRoot = DeletedTree;
    DeletedTree = DeletedTree->LeftChild;
    free(OldRoot);

    DeletedQueue = Initialize();
    DeletedQueue->CurrentSize = (1 << MinTree) - 1;
    for (j = MinTree - 1; j >= 0; --j) {
        DeletedQueue->TheTrees[j] = DeletedTree;
        DeletedTree = DeletedTree->NextSibling;
        DeletedQueue->TheTrees[j]->NextSibling = NULL;
    }

    H->TheTrees[MinTree] = NULL;
    H->CurrentSize -= DeletedQueue->CurrentSize + 1;

    Merge(H, DeletedQueue);

    return MinItem;
}

BinTree CombineTrees(BinTree T1, BinTree T2) {
    if (T1->Element > T2->Element) {
        return CombineTrees(T2, T1);
    }

    T2->NextSibling = T1->LeftChild;
    T1->LeftChild = T2;

    return T1;
}

BinQueue Merge(BinQueue H1, BinQueue H2) {
    BinTree T1;
    BinTree T2;
    BinTree Carry = NULL;
    int i;
    int j;

    if (H1->CurrentSize + H2->CurrentSize > Capacity) {
        Error("Merge would exceed capacity");
    }

    H1->CurrentSize += H2->CurrentSize;
    for (i = 0, j = 1; j <= H1->CurrentSize; ++i, j *= 2) {
        T1 = H1->TheTrees[i];
        T2 = H2->TheTrees[i];

        switch (!!T1 + 2 * !!T2 + 4 * !!Carry) {
        case 0:  /* No trees */
        case 1:  /* Only H1 */
            break;
        case 2:  /* Only H2 */
            H1->TheTrees[i] = T2;
            H2->TheTrees[i] = NULL;
            break;
        case 4:  /* Only Carry */
            H1->TheTrees[i] = Carry;
            Carry = NULL;
            break;
        case 3:  /* H1 and H2 */
            Carry = CombineTrees(T1, T2);
            H1->TheTrees[i] = NULL;
            H2->TheTrees[i] = NULL;
            break;
        case 5:  /* H1 and Carry */
            Carry = CombineTrees(T1, Carry);
            H1->TheTrees[i] = NULL;
            break;
        case 6:  /* H2 and Carry */
            Carry = CombineTrees(T2, Carry);
            H2->TheTrees[i] = NULL;
            break;
        case 7:  /* All three */
            H1->TheTrees[i] = Carry;
            Carry = CombineTrees(T1, T2);
            H2->TheTrees[i] = NULL;
            break;
        default:
            break;
        }
    }

    return H1;
}

ElementType FindMin(BinQueue H) {
    int i;
    ElementType MinItem;

    if (IsEmpty(H)) {
        Error("Empty binomial queue");
        return 0;
    }

    MinItem = Infinity;
    for (i = 0; i < MaxTrees; ++i) {
        if (H->TheTrees[i] != NULL &&
            H->TheTrees[i]->Element < MinItem) {
            MinItem = H->TheTrees[i]->Element;
        }
    }

    return MinItem;
}

int IsEmpty(BinQueue H) {
    return H->CurrentSize == 0;
}

int IsFull(BinQueue H) {
    return H->CurrentSize == Capacity;
}

void PrintBinTree(BinTree T, int depth) {
    int i;

    if (T == NULL) {
        return;
    }

    for (i = 0; i < depth; ++i) {
        printf("    ");
    }

    printf("%02d\n", T->Element);

    PrintBinTree(T->LeftChild, depth + 1);
    PrintBinTree(T->NextSibling, depth);
}

void PrintBinQueue(BinQueue H, int depth) {
    int i;

    if (H == NULL) {
        printf("BinomialQueue is empty!\n");
        return;
    }

    printf("----------------------\n");
    for (i = 0; i < MaxTrees; ++i) {
        if (H->TheTrees[i] != NULL) {
            PrintBinTree(H->TheTrees[i], 0);
            printf("----------------------\n");
        }
    }
}

// EOF

